<?php
/** 
* @file NTree.class.php
* @author kenlixin@gmail.com
* @version 0.1 design
* @date 2009-11-23
*/

class NTree{
    
    /** 
    * @db and other setting: must be use ThinkPHP Model Class or adapter.
    * @param 'db'
    * @param 'table'
    * @param 'key'
    * @param 'left'
    * @param 'right'
    */
    private $_setting = array(
        '_db'        =>  'localhost',
        '_user'      =>  'root',
        '_password'  =>  '',
        '_table'     =>  'nested_category',
        '_key'       =>  'id',
        '_left'      =>  'lft',
        '_right'     =>  'rgt',
        '_model'     =>  'Model',
        'title'      =>  'title',   
    );

    public function __construct(){
        if( func_num_args>0 && is_array(func_get_arg(0)) ){           
            $argArr = fun_get_arg(0);
            
            foreach($argArr as $key=>$item){
                if(isset($this->_setting['_'.$key])){ $this->_setting['_'.$key] = $item; }    
            }
        }
    }

    public function isNode($node){
        extract($this->_setting);
        if( is_array($node) && isset($node[$_key]) && isset($node[$_left]) &&  isset($node[$_right]) ){
            return true;
        }else{
            return false;
        }
    }

    public function getNode($key){

        extract($this->_setting);

        $sql    =   "SELECT * FROM `$_table` WHERE `$_key` = $key;";
        $m      =   new $_model();
        $record =   $m->query($sql);
        $result =   count($record)>0 ? $record[0]:null;

        return $result;
    } 

    public function getRootNode(){
        extract($this->_setting);
        
        $sql        =   "SELECT * FROM `$_table` WHERE  `$_right` = (SELECT MAX(`$_right`) FROM `$_table`);";
        $model      =   new $_model();
        $record     =   $model->query($sql);
        $result     =   count($record)>0? $record[0]:null;
        
        return $result;
    }

    public function getParentNode($node){
        if($this->isNode($node) == false){return null;}

        extract($this->_setting);
        $node_lft   =   $node[$_left];
        $node_rgt   =   $node[$_right];

        $sql        =  "SELECT * FROM `$_table` WHERE `$_right`=(SELECT MIN(`$_right`) FROM `{$_table}` WHERE `$_left`<$node_lft AND `$_right`>$node_rgt ) ORDER BY {$_left} ASC; ";
        //dump($sql);
        
        $model      =   new $_model();
        $record     =   $model->query($sql);
        $result     =   count($record)>0? $record[0] : null;

        return $result;
    }   //    getParentNode

    public function getNodePath($node){

        if($this->isNode($node)){return null;}
        
        extract($this->_setting);

        $node_lft   =   $node[$_left];
        $node_rgt   =   $node[$_right];

        $sql        =   "SELECT * FROM `$_table` WHERE `$_left`<$node_lft AND `$_right`>$node_rgt;";
        //dump($sql);

        $model      =   new $_model();
        $rescord    =   $model->query($sql);
        $result     =   count($record)>0 ? $record:null;

        return $result;    
    }     //  getNodePath


    public function getAllNodes(){
        extract($this->_setting);

        $sql        =   "SELECT * FROM `$_table` ORDER BY `$_left` ASC;";
        //dump($sql);

        $model      =   new $_model();
        $record     =   $model->query($sql);
        $result     =   count($record)>0 ? $record : null;

        return $result;
    }  
     
    public function getSubNodes($node){
        
        if($this->isNode($node) == false){return null;}

        extract($this->_setting);
         
        $node_lft   =   $node[$_left];
        $node_rgt   =   $node[$_right];

        $sql        =   "SELECT * FROM `$_table` WHERE `$_left` BETWEEN $node_lft AND $node_rgt ORDER BY `$_left` ASC;";
        $model      =   new $_model();
        $record     =   $model->query($sql);
        $result     =   count($record)>0?$record:null;
        
        return $result; 
    } 

    public function getSameLevelNodes($node){
        
        if($this->isNode($node) == false){return null;}
        
        extract($this->_setting);

        $parentNode = $this->getParentNode($node);
        if($this->isNode($parentNodes) == false ){return $node;}

        $subNodes = $this->getSubNodes($parentNode); 
        array_shift($subNodes);

        $stack = $parentNode[$_right];
        $result = array();
        foreach($subNodes as $item){
            if($item[$_right]>$stack){
                $stack=$item[$_right];
                $result[]=$item;
            }
        }
        return $result;
    }    

    public function displaySubTree($node){
        if($this->isNode($node == false)){return null;}

        extract($this->_setting);

        $result = array();
        $stack = array();

        $nodes = $this->getSubNodes($node); 
        
        foreach($nodes as $row){
            if(count($stack)>0){
                while($stack[count($stack)-1] < $row[$_right]){
                    array_pop($stack);
                }
            }
            $result[] = str_repeat('--', count($stack)) . $row['title'];
            $stack[]    =   $row[$_right];
        }

        return $result;
    }

    public function displayTree(){
        return $this->displaySubTree($this->getRootNode()); 
    }

    
    public function getAllChildCount($node){
        extract($this->_setting);
        return ( $node[$_right] - $node[$_left] - 1 )/2;
    }

    /** 
    * @brief insertNode class, default position is 'after'.
    * 
    * @param $targetNode
    * @param $referNode
    * @param $position after|before|below.
    * 
    * @return 
    */
    public function insertNode($targetNode, $referNode, $position='after'){
        

        if($this->isNode($referNode) == false){ return null; }
        
        extract($this->_setting);
        
        /*
         * 插入为参考节点后的兄弟节点
         */
        if($position =='after'){
           
            //1.取得$referNode的父元素$referParentNode
            $referParentNode = $this->getParentNode($referNode); dump($referParentNode);
            $referRight = $referParentNode[$_right];    //参考右值

            //2.生成$targetNode值:
            //          1).排除$targetNode[$_key]
            //          2).生成left, 规则为left = referRight + 1
            //          3).生成right, 规则为right = referRight + 2
            //          4).与tagetNode 合并成为insertNode
            $insertNode = array_merge( array_diff($targetNode, array($_key=>'')),  array($_left=>$referRight+1, $_right=>$referRight+2) );
            dump($insertNode);

            //3.更新,规则如下:
            //              1).更新left,所有left>$referParentNode[right]的节点,left=left+2
            //              2).更新right,所有right>$referParentNode[right]的节点,right+right+2

            $sqlUpdateLeft  = "UPDATE `$_table` SET `$_left`=`$_left`+2 WHERE `$_left`>$referRight;";     dump($sqlUpdateLeft);
            $sqlUpdateRight = "UPDATE `$_table` SET `$_right`=`$_right`+2 WHERE `$_right`>$referRight;";  dump($sqlUpdateRight);
            
            //4.插入
            //      1).生成字段名
            //      2).生成字段值
            //      3).生成SQL 语句
            
            //1).字段名
            $insertFields = array_keys($targetNode);
            foreach($insertFields as $key=>$item){
                $insertFields[$key] = "`$item`";
            }
            $insertFields = implode(',', $insertFields);
            dump($insertFields);

            //2).字段值
            $insertValues = array_values($targetNode);
            foreach($insertValues as $key=>$item){
                $insertValues = is_string($item)? "'$item'" : $item;
            }
            //3).SQL
            $sqlInsert = "INSERT INTO `$_table` ($insertFields) VALUES($insertValues)";
            dump($sqlInsert); 
        } // if(after)

        /*
         * 插入为参考节点前的兄弟节点
         * 规则:
         *  1).更新左值:所有左值大于(参考节点左值-1)的节点,左值+2
         *  2).更新右值:
         *  3).插入:左值=参考节点左值,右值=参考节点左值+2
         */
        if($position =='before'){
            
            $refterLeft = $referNode[$_left]-1;
            
            $sqlUpdateLeft = "UPDATE `$_table` SET `$_left`=`$_left`+2 WHERE `$_left`>$referLeft";
            $sqlUpdateRight = "UPDATE `$_table` SET `$_right`=`$_right`+2 WHERE `$_right`>$referLeft";
            
            $insert = array_merge( array_diff_key($targetNode, array($_key=>'')), array($_left=>$referLeft+1, $_right=>$referLeft+2));
            
            $insertFields = array_keys($insert);
            foreach($insertFields as $key=>$item){$insertFields[$key]='`'.$item.'`';}
            $insertFields   =   implode(',', $insertFields);
            
            $insertValues   =   array_values($insert); //dump($insertValues);
            foreach($insertValues as $key=>$item){
                $insertValues[$key] = is_string($item) ? "'$item'" : $item;
            }
            $insertValues   =   implode(',',$insertValues);
            //dump($insertValues);
            
            $sqlInsert      =   "INSERT INTO `$_table` ($insertFields) VALUES($insertValues);";  dump($sqlInsert);
                
        
        } //if(before)

        /*
         *插入为参考节点最后一个子节点
         */
        if($position == 'below'){
             
            //$referNode 最后一个子元素的右值
            $referRight = $referNode[$_right]-1;
            
            //所有left大于参考节点最后一个子元素的右值的节点,都更新为原值+2    
            $sqlUpdateLeft      =   "UPDATE `$_table` SET `$_left`=`$_left`+2 WHERE `$_left`>{$referRight};";  //dump($sqlUpdateLeft);
            
            //所有right大于参考节最后一个子元素的右值的节点,更新为原值+2
            $sqlUpdateRight     =   "UPDATE `$_table` SET `$_right`=`$_right`+2 WHERE `$_right`>{$referRight};";  //dump($sqlUpdateRight);
            
           
            /* step 1.
             * 排除_setting[key],根据$refer生成_setting[left,right]两个值, left=$referRight+1, right=$referRight+2; 合并$insert
             */
            $insert = array_merge(array_diff_key($targetNode, array($_key=>'')), array($_left=>$referRight+1, $_right=>$referRight+2));    //dump($insertMerge);

            /* step 2.
             * 生成SQL INSERT 语句 字段名
             */
            //取键名
            $insertFields   =   array_keys($insert);
            //加``,为了后面构造 SQL Insert 语句
            foreach($insertFields as $key=>$item){$insertFields[$key]='`'.$item.'`';}
            //格式化为字符串
            $insertFields   =   implode(',', $insertFields);
            //dump($insertFields);

            /* step 3.
             * 生成SQL INSERT 语句 值
             */
            //取值
            $insertValues   =   array_values($insert); //dump($insertValues);
            //给为字符串类型的元素,添加'',为了后面构造 SQL Insert语句.
            foreach($insertValues as $key=>$item){
                $insertValues[$key] = is_string($item) ? "'$item'" : $item;
            }
            //格式化为字符串
            $insertValues   =   implode(',',$insertValues);
            //dump($insertValues);
            
            /* step 4.
             * 生成SQL INSERT 语句
             */
            $sqlInsert      =   "INSERT INTO `$_table` ($insertFields) VALUES($insertValues);";  dump($sqlInsert);

            $model      =   new $_model();
            /*
            try{
                $model->startTrans();
                $model->execute($sqlUpdateLeft);
                $model->execute($sqlUpdateRight);
                $model->execute($sqlInsert);
                $model->commit();
            }catch(Exception $e){   
                throw $e;
            }
            */
            
        } // if(below)
    }

    /** 
    * @brief 
    * 
    * @param $targetNode
    * @param $referNode
    * @param $positiong
    *   -after:在$referNode之后
    *   -before:在$referNode之前
    *   -below:在$referNode之下
    * 
    * @return true|false. 
    */
    public function moveNode($targetNode, $referNode, $position='after'){

    }

    public function deleteNode($node){
       
        extract($this->_setting);

        $nodeLeft       =   $node[$_left];
        $nodeRight      =   $node[$_right];
        $width          =   $nodeRight - $nodeLeft +1;

        $sqlDelete              = "DELETE FROM `$_table` WHERE `$_left` BETWEEN $nodeLeft AND $nodeRight;";  //dump($sqlDelete);
        $sqlUpdateLeftValues    = "UPDATE `$_table` SET `$_right`=`$_right`-$width WHERE `$_right`>$nodeRight;";  //dump($sqlUpdateLeftValues);
        $sqlUpdateRightValues   = "UPDATE `$_table` SET `$_left`=`$_left`-$width WHERE `$_left`>$nodeRight;";  //dump($sqlUpdateRightValues); 

        $model = new Model();

        try{
            $model->startTrans();
            $model->execute($sqlDelete);
            $model->execute($sqlUpdateLeftValues);
            $model->execute($sqlUpdateRightValues);
            $model->commit();
            return true;
        }catch(Exception $e){
            throw $e;
            return false;
        }
    }

}
